package com.zp.self.module.level_4_算法练习.数据结构.链表;

/**
 * @author By ZengPeng
 */
public class 力扣_203_移除链表元素 {
    //测试
    public static void main(String[] args) {
        ListNode node = ListNode.getNode();
        ListNode listNode = new 力扣_203_移除链表元素().removeElements2(node, 1);
        System.out.println(listNode);
    }

    /**
     * 题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
     *
     *
     * 分析：
     *      1.遍历链表，A.记录上一个节点，当当前节点符合删除条件时，上一个节点要指向下一个节点
     *                  B.当前节点的下一个节点!=null ,下一个节点符合删除条件时，currentNode.next = currentNode.next.next;
     *          1.循环条件: node !=null
     *          2.单步操作: currentNode.next = currentNode.next.next;
     *          3.终止操作: currentNode.next ==null
     *
     *      #大神解法：递归？？？
     *
     * 边界值注意：
     *      1. head 为null
     *      2.全部要删除
     **/
    public ListNode removeElements(ListNode head, int val) {
        ListNode currentNode = head;
        ListNode proNode = null;
        while (currentNode!=null){
            if(currentNode.val ==val){
                if(proNode==null)
                    head = currentNode.next;//头节点改变
                else
                    proNode.next = currentNode.next;//上一个节点要指向下一个节点
            }else
                proNode =currentNode;
            currentNode = currentNode.next;  //当前节点如果处理
        }
        return  head;
    }

    // #大神解法：递归
    //   分析：
    //      深度 = 长度  可能会溢出啊   ,
    //      栈还需要消耗内存啊  ，所以此递归不如：记录上一个节点的方法
    public ListNode removeElements2(ListNode head, int val) {
        if(head==null) return null;
        if(head.val==val)
             return  removeElements2(head.next,val);
        else
            head.next = removeElements2(head.next,val);
        return  head;
    }
}
